class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val){
        this.val = val;
    }
  }

public class Test {
    /*
    题目 1 ：比较版本号
     */
    // 1.02.11
    // 1.02.010
    public int compare (String version1, String version2) {
        int v1 = 0;
        int v2 = 0;

        int len1 = version1.length();
        int len2 = version2.length();

        while(v1 < len1 || v2 < len2){
            long sum1 = 0;
            while(v1 < len1 && version1.charAt(v1) != '.'){
                sum1 = sum1 * 10 + (version1.charAt(v1) - '0');
                v1++;
            }
            v1++;

            long sum2 = 0;
            while(v2 < len2 && version2.charAt(v2) != '.'){
                sum2 = sum2 * 10 + (version2.charAt(v2) - '0');
                v2++;
            }
            v2++;

            if(sum1 > sum2){
                return 1;
            }
            if(sum1 < sum2){
                return -1;
            }
        }
        return 0;
    }

    /*
    题目 2 ：数组中的逆序对
     */
    static int count = 0;
    public static int InversePairs(int [] array) {
        //长度小于 2 时， 没有逆序对！
        if(array.length < 2){
            return 0;
        }

        mergerSort(array, 0 , array.length - 1);
        return count;
    }

    public static void mergerSort(int[] array, int left, int right){
        // 中点的坐标习惯这么写：
        //int mid = (left + right) / 2;  //两个没有超过int 最大范围的数字相加很容易超过范围
        // 所以最好写作以下形式：
        int mid = left + (right - left)/2;

        if(left < right){
            //递归数组中的左半部分
            mergerSort(array, left, mid);
            //递归数组中的右半部分
            mergerSort(array, mid + 1, right);
            //合并
            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right){
        //创建一个临时数组：
        int[] temp = new int[right - left + 1];
        //临时下标:
        int c = 0;
        // 保留左下标的数值：
        int l = left;
        //需要合并的左半部分的起始下标：
        int s = left;
        //需要合并的右半部分的起始下标：
        int e = mid + 1;

        while(s <= mid && e <= right){
            // 如果左半部分的值小于或者等于右半部分的值，那就没有逆序对！
            if(array[s] <= array[e]){
                temp[c++] = array[s++];

            }else{
                // 有逆序对的情况：
                temp[c++] = array[e++];
                count += mid - s + 1;
                // 题目要求要 mod 1000000007
                count %= 1000000007;
            }
        }

        while(s <= mid){
            temp[c++] = array[s++];
        }

        while(e <= right){
            temp[c++] = array[e++];
        }

        for(int x : temp){
            array[l++] = x;
        }
    }

    public static void main(String[] args) {
        int[] arr = {8,7,6,5,4,3,2,1};
        int ret = InversePairs(arr);
        System.out.println(ret);
    }

    /*
    题目 3 ：二分查找-Ⅰ
     */
    //实现无重复数字的升序数组的二分查找
    public int search (int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    /*
    题目 4：寻找峰值
     */
    // 二分查找
    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[mid + 1]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    /*
    题目 5：合并二叉树
     */
    public static TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1 == null){
            return t2;
        }
        if(t2 == null){
            return t1;
        }

        TreeNode head = new TreeNode(t1.val + t2.val);
        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);
        return head;
    }

   

}
